package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//4ms 86%,4.5MB 35%
func pathSum(root *TreeNode, target int) [][]int {
	if root == nil {
		return nil
	}
	res := [][]int{}
	var check func(*TreeNode, int, []int)
	check = func(node *TreeNode, sum int, tmp []int) {
		sum += node.Val
		tmp = append(tmp, node.Val)
		if node.Left != nil {
			check(node.Left, sum, tmp)
		}
		if node.Right != nil {
			check(node.Right, sum, tmp)
		}
		if sum == target && node.Left == nil && node.Right == nil {
			res = append(res, append([]int(nil), tmp...))
		}
	}
	check(root, 0, []int{})
	return res
}

func main() {
	fmt.Println(pathSum(&TreeNode{1, nil, nil}, 1))
}
